package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author 郭辉
 * @className TODO
 * @description 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 示例 2：
 *
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 *
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 *
 *
 * 提示：
 *
 * 0 <= digits.length <= 4
 * digits[i] 是范围 ['2', '9'] 的一个数字。
 * 通过次数667,900提交次数1,150,833
 * @date 2023/4/1 11:19
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet17 {

    private static Map<Integer,List<Character>> map = new HashMap<>();
    static {
        Character[] characters = {'a', 'b', 'c'};
        map.put(2, Arrays.asList(characters));
        characters = new Character[]{'d', 'e', 'f'};
        map.put(3, Arrays.asList(characters));
        characters = new Character[]{'g', 'h','i'};
        map.put(4, Arrays.asList(characters));
        characters = new Character[]{'j','k', 'l'};
        map.put(5, Arrays.asList(characters));
        characters = new Character[]{'m', 'n','o'};
        map.put(6, Arrays.asList(characters));
        characters = new Character[]{'p', 'q','r','s'};
        map.put(7, Arrays.asList(characters));
        characters = new Character[]{'t','u','v'};
        map.put(8, Arrays.asList(characters));
        characters = new Character[]{'w','x','y', 'z'};
        map.put(9, Arrays.asList(characters));
    }

    List<List<Character>> res = new ArrayList<>();
    List<String> sRes = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.equals("")){
            return sRes;
        }
        char[] chars = digits.toCharArray();
        List<List<Character>> choose = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            List<Character> list = map.get(Integer.valueOf(chars[i]) - 48);
            choose.add(list);
        }
        combinations(choose,0,new ArrayList<Character>());
        for (int i = 0; i < res.size(); i++) {
            String tem = "";
            for (int j = 0; j < res.get(i).size(); j++) {
                tem += res.get(i).get(j);
            }
            sRes.add(tem);
        }
//        Iterator<Map<Character, Integer>> iterator = res.iterator();
//        while (iterator.hasNext()){
//            Map<Character, Integer> next = iterator.next();
//
//            Iterator<Map.Entry<Character, Integer>> mapIterator = next.entrySet().iterator();
//            String tem = "";
//            while (mapIterator.hasNext()){
//                Map.Entry<Character, Integer> mapNext = mapIterator.next();
//                for (int i = 0; i < mapNext.getValue(); i++) {
//                    tem += mapNext.getKey();
//                }
//            }
//            sRes.add(tem);
//        }
        return sRes;
    }

    // 选择
    // 路径
    // 返回条件
    public void combinations(List<List<Character>> choose, int row, List<Character> track) {

        //返回条件
        if (track.size() == choose.size()){
            List<Character> tem = new ArrayList<>();
            tem.addAll(track);
            res.add(tem);
            return;
        }
        for (int i = 0; i < choose.get(row).size(); i++) {
            //剪枝
//            if (track.contains(choose.get(row).get(i))){
//                continue;
//            }

            //选择
            track.add(choose.get(row).get(i));
            combinations(choose,row+1,track);
            //撤销选择
            track.remove(track.size()-1);
        }

    }

    public static void main(String[] args) {
        Leet17 leet17 = new Leet17();
        System.out.println(leet17.letterCombinations("2"));
//        System.out.println((char)97);
    }
}
